------------A*寻路算法------------------

local M = {}

local NodeClass=require(script.Node)

local function Remove(t,element)
	for i,e in pairs(t) do
		if e==element then
			table.remove(t,i)
			return 
		end
	end
end

local function Contains(t,element)
	for i,e in pairs(t) do
		if e==element then
			return  true
		end
	end
	return false
end

local function GetPath(start,tag,distanceFuc,endFuc,walkebleFuc)
	local tosearch={} --搜寻表
	table.insert(tosearch,start) --讲起点加入搜寻表
	local processed={} --已搜寻表
	
	while #tosearch>0  do --如果搜寻表有点，则持续搜索
		
		local current=tosearch[1] --选择一个点 进行搜寻
		
		for _,t in pairs(tosearch) do
			--选择代价最小，代价相等情况 选择预估值 更小的节点作为搜寻点
			if t:F()<current:F() or (t:F()==current:F() and t.H< current.H) then
				current=t
			end
		end
		
		table.insert(processed,current)
		Remove(tosearch,current)
		
		
		if endFuc(current,tag) then
			
			local p=current
			local path={}

			while true do
				if p==start then
					NodeClass.clear()
					local newpath={}
					for i=#path,1,-1 do
						table.insert(newpath,path[i])
					end
					return newpath
				end
				table.insert(path,p.__inst)
				p=p.Connection
			end
		end
		--if current==tag then --已寻到目标点
		--	local p=tag
		--	local path={}
			
		--	while true do
		--		if p==start then
		--			NodeClass.clear()
		--			return path
		--		end
		--		table.insert(path,p.__inst)
		--		p=p.Connection
		--	end
		--end		

		for k,n in pairs(current:Neighbor()) do --遍历邻居
			if walkebleFuc(n) and not Contains(processed,n) then --能够行走且没在已搜寻表内
				local inSearch=Contains(tosearch,n)
				local cosToNeighbor=current.G+current:GetDistance(n)
				if not inSearch or cosToNeighbor<n.G  then
					n.G=cosToNeighbor
					n:SetConnection(current)
					if not inSearch then
						--n.H=n:GetDistance(tag)
						
						if distanceFuc(n,tag) then
							NodeClass.clear()
							return nil
						end
						
						table.insert(tosearch,n)
					end
				end
				
			end
		end
		
	end
	NodeClass.clear()
	return nil
end

M.FindPath=function(start,tag,...)
	return GetPath(NodeClass.new(start,...),NodeClass.new(tag,...),function(n,tag)
		n.H=n:GetDistance(tag)
		return false
	end,function(current,tag)
		return current==tag
	end,function(n)
		return n:Walkeble()
	end)
end

M.FindNodePathCondition=function(start,tag,distanceFuc,endFuc,walkebleFuc,...)
	if not walkebleFuc then
		walkebleFuc=function(n)
			return n:Walkeble()
		end
	end
	return GetPath(NodeClass.new(start,...),NodeClass.new(tag,...),distanceFuc,endFuc,walkebleFuc)
end

return M
